Communication systems or networks, such as those used to deliver telecommunications, to deliver video images, to interconnect computers, to provide conventional cellular communications, and the like, include any number of nodes. These networks deliver electronic communications between two points by routing the communications content from node to node within the network. As the number of nodes in a network increases and as the number of communication paths available to each network node increases, the number of potential paths available for delivering any single communication likewise increases. As the number of potential paths which are available increases, a problem of selecting an appropriate path through the network arises.
Typically, it is advantageous for the network to attempt to select the shortest possible path to minimize delay, to consume a minimal amount of network resources, and to maximize reliability in delivering communications, information flow, or other service. At the same time, actions within the network need to balance the constraints of the delay, resource consumption, and reliability with the need to prevent overloading any of the network nodes or communication links, while maintaining delivery of the network traffic. Delivery of network traffic to its intended destination is desirably made with proper allowances for statistical variations in traffic and an ability for the network to absorb instantaneous changes in requested service without having to react to the volume of traffic by devising new routing instructions.
Packet routing techniques in dynamic or moving communication systems have generally required near real-time exchange of routing update information among the communication nodes. Other packet routing techniques have required significant decision making and packet processing in the communication nodes. These techniques require significantly more resources and increase the complexity of the communication nodes. In a global communication system where nodes are space-based, minimal exchange of routing information between the nodes is desirable in order to minimize node complexity, simplify routing management, and reduce resources required for the exchange of routing information.
Alternative routing techniques that have been used in communication systems include centralized routing where updated routing tables are calculated in a centralized location and sent to each node. Examples of this include packet routing networks such as Tymnet. However, in ground based communication networks such as in Tymnet, all calls are normally processed by a single central supervisor which calculates and maintains the updated route information for each possible source-destination pair in the network. Since that single resource selects routes for each communication and assigns so-called "virtual circuit" identifiers to each, the uniqueness of such route identification is maintained for all communication needs throughout the network, and no confusion is created when several communications cross simultaneously through one intermediate node on their journey through the network. In satellite-based communication networks, the complexity and inefficiency associated with real-time exchange of route information among remotely located nodes is undesirable.
Generally, most routing tables, such as minimum hop tables, are generated so that minimal delay in transporting data packets among the communication nodes. However, in dynamic or moving communication systems, minimum hops alone are not sufficient for designing routing tables. One disadvantage to minimum hop tables is that all hops are treated equally and the dynamic aspects of the system are ignored. For example, when the communication nodes are moving, delays between the nodes change and links connecting the nodes are either turned on or shut down. Traditional packet routing systems that use routing tables do not take into account changes in the connectivity among the nodes, as in dynamic or moving systems.
Another disadvantage to traditional routing tables is that the capacity of the links is not considered. Minimum hop tables route data packets along predetermined routes regardless of the amount of traffic on certain links. As a result, some links become overloaded while other links are far below capacity. These traditional methods do not take into account actual or historical traffic levels.
Furthermore, the use of traditional routing tables is inefficient for several reasons because, among other things, data packets from several sources take different routes to reach the same destination. In some situations, data packets directed to a single destination node may be traveling both directions on one communication link in the network. Data packets directed to the same communication node traveling in both directions on a communication link is a wasted transport.
Thus what is needed are an apparatus and method for routing data packets in a dynamic and moving communication system. What is also needed are an apparatus and method for routing data packets that accommodate changes in the connectivity between the communication nodes. Desirably, changing capacity of links should also be considered.
Thus what is also needed are an apparatus and method for routing data packets that accommodate actual or historical traffic demand. What is also needed are a method and apparatus that prevents link overloads accommodating link capacity and actual traffic. What is also needed are an apparatus and method for routing data packets that are responsive to changes in system traffic.
Thus what is also needed are an apparatus and method for routing data packets that reduces the amount of data packets having the same destination traveling in both directions on one communication link. What is also needed are a routing apparatus and method which achieves uniformity in the usage of network links while limiting the number of hops between source and destination.